package practice.sort.compare;

import practice.sort.Sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/10 09:54
 */
public class ShellSort extends Sort {
    @Override
    public void sort() {
        List<Integer> steps = stepSequence();
        for (int i = 0; i < steps.size(); i++) {
            sort(steps.get(i));
        }
    }

    public void sort(int step) {
        for (int col = 0; col < step; col++) {
            for (int cur = col + step; cur < nums.length; cur += step) {
                while (cur > col && nums[cur] < nums[cur - step]) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    public List<Integer> stepSequence() {
        List<Integer> steps = new ArrayList<>();
        int step = nums.length;
        while ((step >>= 1) > 0) {
            steps.add(step);
        }
        return steps;
    }
}
